/**
 * @author: Colmenares Carlos (carlos.a.colmenares.r@gmail.com)
 *
 * Header for the n-queens solver
 */
#ifndef _N_AMAZON_SOLVER_
#define _N_AMAZON_SOLVER_

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>

#define TRUE 1
#define FALSE 0

/**
 * The size of the board to be solved
 */
int N;

/**
 * The number of conflicts on the board
 */
int tot_conflicts;

/**
 * Heuristic number, used as a limit to recalculate
 * the "attacked" array
 */
const double C1 =  0.45;

/**
 * Heuristic number, used for detecting when the
 * algorithm gets trapped in a local minimum
 */
const int C2 = 35;

/**
 * Heuristic number, used for stopping re-calculations
 * of the 'attacked' array when the number of conflicts
 * is small
 */
const int C3 = 100;

/**
 * Heuristic number, used as an upper bound for the
 * number of retries when placing a conflicts-free
 * queen in the initial board.
 */
const int C4 = 100000;

/**
 * Heuristic number, after this number of iterations
 * a new random seed is generated
 */
const int C5 = 200000;

/**
 * The array that represent the rows of
 * the board where each queen is placed,
 * queen[i] will contain the column where
 * the queen of the ith row is placed.
 * (i, queens[i])
 */
int *queens;

/**
 * Each cell in this array represents a
 * positive diagonal on the board, the
 * number in each cell is the number of
 * queens on the respective diagonal
 */
int *pos_diag;

/**
 * Each cell in this array represents a
 * negative diagonal on the board, the
 * number in each cell is the number of
 * queens on the respective diagonal.
 */
int *neg_diag;

/**
 * This array is used for keeping track of
 * the conflicted queens, which will be considered
 * for swap operations.
 */
int *attacked;

/**
 * True if the final board should be printed
 */
int print_board = FALSE;

/**
 * True if the final solution should be printed
 */
int print_solution = FALSE;

/**
 * True if information about the algorithm results
 * should be printed
 */
int print_info = FALSE;

/**
 * Print the usage of the program, indicating the
 * possible flags and their meaning
 */
inline void print_usage();

/**
 * This function generates a 'random' initial
 * board using a greedy algorithm and placing
 * the correct values in the three arrays:
 * queens, pos_diag and neg_diag.
 */
inline void gen_init_board();

/**
 * Returns the number of conflicts that a queen has
 * @param y     The row of the queen
 * @return      The number of conflicts
 */
int num_conflicts(int y);

/**
 * Swaps two queens and actualizes
 * all the arrays
 * @param a1    Row of first queen
 * @param a2    Row of second queen
 */
void swap_queens(int a1, int a2);

/**
 * Makes random swaps to the board
 * @return  The number of conflicts in the new
 *          board
 */
int randomize_board();

/**
 * Computes the number of conflicted queens
 * and fills the array 'attacked' with it's
 * row numbers
 * @return  The number of conflicted queens
 *          on the board
 */
int compute_attacks();

#endif
